package com.study.lintcode.my.code_20;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**********************************************************************
 * &lt;p&gt;文件名：Example_15.java &lt;/p&gt;
 * &lt;p&gt;文件描述：(描述该文件做什么) 
 * @project_name：LintCode
 * @author zengshunyao
 * @create 2019/1/6 1:18 
 * @history
 * @department：政务事业部
 * Copyright ChengDu Funi Cloud Code Technology Development CO.,LTD 2014 
 *                    All Rights Reserved.
 */
public class Example_15 {
    public int count = 0;

    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if (nums == null)
            return res;
        if (nums.length == 0) {
            res.add(new LinkedList<Integer>());
            return res;
        }

        List<Integer> list = new LinkedList<Integer>();
        //1.0
        dfs(res, list, nums, 0);
        //2.0
//        xunhuan(res, list, nums);

        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, int begin) {
        count++;
        int n = nums.length;
        if (list.size() == n) {
            res.add(new LinkedList<Integer>(list));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (list.contains(nums[i]))
                continue;
            list.add(nums[i]);
            dfs(res, list, nums, begin + 1);
            list.remove(list.size() - 1);
        }
    }

    private void xunhuan(List<List<Integer>> result, List<Integer> list, int[] nums) {
        //非递归实现的方法，思路如下：也就是使用插入法，假如传进去的数字是1，2，3，那么先把1放进去list中得到【1】，
        // 把【1】放到list（存放list的list）中得到【【1】】然后取出【【1】】里面的第一个list【1】，往里面插入2,这个数字，有两种插法，
        // 就产生了两种排列【1,2】【2,1】，放进去得到【【1,2】，【2,1】】，然后取出【1,2】，插入3，有三种情况【3,1,2】，【1,3,2】，【1,2,3】,
        // 把它们放进去就是【【2,1】，【3,1,2】，【1,3,2】，【1,2,3】】，接着把【2,1】取出来，将3插进去，也有3中插法，
        // 就得到了最后的排列【【3,1,2】，【1,3,2】，【1,2,3】，【3,2,1】，【2,3,1】，【2,1,3】】，直到这里数组中的元素已经全部插入完毕。
        //---------------------
        //作者：秦怀
        //来源：CSDN
        //原文：https://blog.csdn.net/Aphysia/article/details/77774105
        //版权声明：本文为博主原创文章，转载请附上博文链接！

        list.add(nums[0]);
        result.add(new LinkedList<Integer>(list));
        for (int i = 1; i < nums.length; i++) {
            int sizeOuter = result.size();
            for (int j = 0; j < sizeOuter; j++) {
                //因为第一个是老list
                int sizeInner = result.get(0).size();
                for (int k = 0; k <= sizeInner; k++) {
                    //新new一个list 存放，因此所有位置插完了就必须扔掉老list
                    List<Integer> inner = new LinkedList<Integer>(result.get(0));
                    inner.add(k, nums[i]);
                    result.add(inner);
                }
                result.remove(0);
            }
        }
    }

    public static void main(String[] args) {
        Example_15 example_15 = new Example_15();
        List<List<Integer>> result = example_15.permute(new int[]{1, 2, 3});
        for (List<Integer> list : result) {
            System.out.println(Arrays.toString(list.toArray()));
        }
        System.out.println("递归次数：" + example_15.count);
    }
}
